package h0817;

import java.util.*;

/**
 * @author 不知名帅哥
 * @version 1.0
 * @description 打开转盘锁
 * @date 2024/8/17 18:03
 */
public class OpenLock {

    public static void main(String[] args) {
        String[] deadends = {"0201", "0101", "0102", "1212", "2002"};
        String target = "0202";
        System.out.println(openLock(deadends, target));
    }


    public static int openLock(String[] deadends, String target) {
        Set<String> deadSet = new HashSet<>(Arrays.asList(deadends));
        Set<String> visited = new HashSet<>();

        //定义存储坐标的序列
        LinkedList<int[]> queue = new LinkedList<>();

        int[][] directions = new int[][]{
                {-1, 0, 0, 0},
                {1, 0, 0, 0},
                {0, -1, 0, 0},
                {0, 1, 0, 0},
                {0, 0, -1, 0},
                {0, 0, 1, 0},
                {0, 0, 0, -1},
                {0, 0, 0, 1},
        };
        //从0000开始
        String start = "0000";
        if (deadSet.contains(start)) return -1;
        queue.addLast(new int[]{0, 0, 0, 0, 0});
        visited.add(start);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] curNode = queue.removeFirst();
                String temp = curNode[0] + "" + curNode[1] + curNode[2] + curNode[3];
                if (temp.equals(target)) {
                    return curNode[4];
                }
                for (int j = 0; j < directions.length; j++) {
                    int a = change(curNode[0] + directions[j][0]);
                    int b = change(curNode[1] + directions[j][1]);
                    int c = change(curNode[2] + directions[j][2]);
                    int d = change(curNode[3] + directions[j][3]);

                    String o = a + "" + b + c + d;
                    if (!deadSet.contains(o) && !visited.contains(o)) {
                        queue.addLast(new int[]{a, b, c, d, curNode[4] + 1});
                        visited.add(o);
                    }
                }
            }
        }
        return -1;
    }

    private static int change(int num) {
        if (num < 0) {
            num = num + 10;
        } else if (num >= 10) {
            num = num % 10;
        }
        return num;
    }
}
